package chapter6;

/**
 * 平面上的回溯法
 * 回溯就是从一个点开始 然后新开一个方法进行递归 有一个索引 用来判断递归的结束 然后里面是一个for循环
 * @author yuh
 * @date 2018/4/26 13:10
 */
public class PlaneCombine {

    static boolean[][] signed;
    static int[][] d = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    static boolean exists(char[][] chars, String inputStr) {
        signed = new boolean[chars.length][chars[0].length];
        for (int i = 0; i < signed.length; i++) {
            for (int j = 0; j < signed[i].length; j++) {
                signed[i][j] = false;
            }
        }
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars[i].length; j++) {
                if (searchWord(chars, i, j, 0, inputStr)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean searchWord(char[][] chars, int i, int j, int index, String inputStr) {
        if (index == inputStr.length() - 1) {
            return chars[i][j] == inputStr.charAt(index);
        }
        char tmpChar = inputStr.charAt(index);
        if (tmpChar == chars[i][j]) {
            signed[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int newX = i + d[k][0];
                int newY = j + d[k][1];
                if (inArea(newX, newY, chars.length, chars[0].length) && !signed[newX][newY]) {
                    if (searchWord(chars, newX, newY, index + 1, inputStr)) {
                        return true;
                    }

                }
            }
        }
        return false;
    }


    private static boolean inArea(int newX, int newY, int length, int length1) {
        return newX > -1 && newY > -1 && newX < length && newY < length1;
    }

    public static void main(String[] args) {
        String inputStr = "ABCFIH";
        char[][] chars = {{'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}};
        System.out.println(exists(chars, inputStr));
    }
}
